The present invention relates in general to enhance efficiency in data processing systems, and in particular to enhance efficiency in performing data bits processing functions. Still more particularly, the present invention relates to a method and an apparatus of enhancing processing efficiency in a data processing system for locating the most, or least, significant bit in a bit string comprising plurality of data bits.
In some computer operations or instructions, the most or least significant set bit on a data word or an array is requested by either an assembly instruction or other component in a microprocessor system. A set bit is defined conventionally as a bit set to "1". For example, in some matrix calculations, leading zeros of a bit-string is preferably to be eliminated in order to conserve memory space. Therefore, the first most significant set bit is needed to be located in order to truncate all the leading zeros. In another example such as floating point processing, leading zeros are generally detected and eliminated. Therefore, a method of efficiently detecting the first most., or least, significant set bit of a group of data bits is desired.
In the Intel (TM) x86 instruction set, there is an instruction Bit Scan Forward ("B SF") for searching an operand for the least significant set bit ("1 " bit). According to the Intel (TM) x86 instruction set, if a least significant 1 bit is found, its bit index is stored in the destination location. The bit index is an unsigned offset from bit 0 of the source operand. If the contents source operand does not contain any set bit, the contents of the destination operand is undefined. For example, in a 32-bit bit-string, the destination operand will be 5 bits long (i.e. S4,S3,S2,S1,S0).
The following algorithm is used to illustrate the detailed operation of the BSF in a conventional processor:
IF SRC = 0 * No set bit? THEN ZF &lt;-- 1; * Set zero bit DEST is undefined; * Result undefined ELSE ZF &lt;-- 0; * Reset zero bit temp &lt;-- 0; * Initialize temp reg WHILE Bit(SRC, temp) = 0 * Bit set? DO temp &lt;-- temp + 1; * Increment temp DEST &lt;-- temp; * Update result OD; * Loop exit FI; * Finish
As shown in the algorithm, the processor tests each bit at a time and then proceeds to the next bit if the condition is not met. As it can be instantly recognized, extensive time delay will occur if the first least significant set bit is in the higher bits range.
Another example is the Intel (TM) instruction BSR where the most significant set bit is detected. The algorithm is similar to the BSF as shown above, with the replacing of the least significant bit with the most significant bit. However, the same timing penalty will be incurred when the set bit is located in some undesirable positions.
Therefore, a more efficient method of locating the most or least significant set bit is desired.